package taller2.model.graph.algorithms;

import java.util.ArrayList;

import taller2.interfaces.Connection;
import taller2.interfaces.Graph;
import taller2.interfaces.InitialNodeApplicator;
import taller2.interfaces.Node;
import taller2.utils.Constants;

public class TopologicBFSApplicator extends AlgorithmApplicatorImpl implements InitialNodeApplicator{
	private static final String path = Constants.savedGraphsPath + "BFSTopo";
	private int initialNode;
	private int cont;
	private boolean directed;
	
	private ArrayList<Node> visited;
	private ArrayList<Integer> incidencias; //cantidad de incidencias de cada nodo
	private ArrayList<Node> listaResultante; //lista con los nodos ordenados topologicamente
	private ArrayList<Node> listaNodosListos; //lista de los nodos visitables (es decir con todos los predecesores visitados)
	
	public TopologicBFSApplicator(){
		super();
		directed = true;
	}

	public void solveProblem(Graph g){
		
		if(noGraph(g) || !noGraphPaths() || !noPseudocodeLines())
			return;
		
		//el algoritmo es solo para grafos acíclicos!
		if (! esAciclico(g)){
			auxText.add("ATENCION! SOLO PARA GRAFOS ACICLICOS");
			return;
		}
		
		//inicializo listas
		visited = new ArrayList<Node>();
		incidencias = new ArrayList<Integer>();
		listaResultante = new ArrayList<Node>();
		listaNodosListos = new ArrayList<Node>();
		
		//preparo el grafo (borro todo lo innecesario)
		g.unselectConnections();
		g.unselectNodes();
		g.killFluxes();
		g.killWeights();
		
		directed = g.isDirected();
		
		//Empieza el algoritmo propiamente dicho
		ArrayList<Node> nodes = g.getNodes();

		for(int i=0; i<nodes.size() ; i++){
			Node node = nodes.get(i);
			node.setId(i);
			//y cargo cuantas aristas incidentes tiene cada nodo
			incidencias.add( g.getConnectionsTo(node).size() );	
			
			//guardo nodos sin aristas entrantes en listaNodosListos
			if (incidencias.get(i) == 0){
				listaNodosListos.add(node);
			}
		}
		
		//si se definio un nodo inicial intento usar ese, sino no importa
		Node start;
		if (initialNode != -1){
			start = nodes.get(initialNode);
			
			if (listaNodosListos.contains(start)){
				//si esta en la lista de listo lo paso al principio de la lista para usarlo
				listaNodosListos.remove(start);
				listaNodosListos.add(0,start);
			}
		}	
			
		//Salvo estado inicial
		g.save(path);
		cont = 0;
		
		guardarPaso(g,1);
		guardarPaso(g,2);
		
		guardarPaso(g,3);
		while (! listaNodosListos.isEmpty()){

			
			Node nodoActual = listaNodosListos.get(0);
			listaNodosListos.remove(0);
			
			pintarArista(nodoActual);
			visited.add(nodoActual);
			nodoActual.select();
			
			guardarPaso(g,4);
			
			//inserto al final de la lista que los tendra en orden topologico
			guardarPaso(g,5);
			listaResultante.add(nodoActual);
			
			//a cada nodo conectado le bajo una incidencia
			guardarPaso(g,6);
			for (Connection connection : nodoActual.getConnections()) {
				Node other = connection.getOtherNode();

				guardarPaso(g,7);
				int inci = incidencias.get(other.getNumberId());
				inci --;
				incidencias.set(other.getNumberId(),inci);
				
				//y si no tiene aristas entrantes lo agrego a la lista de listos
				guardarPaso(g,8);
				if ( incidencias.get(other.getNumberId()) == 0 )  {
					guardarPaso(g,9);
					listaNodosListos.add(other);	
				}
			}
		}
		
		guardarPaso(g,10);
			
		g.load(path);
	}
	
	private void guardarPaso(Graph g, int pcLine){
		cont++;
		saveGraph(g, path + cont);
		pseudocodeLines.add(pcLine);
		auxText.add( "Visitados:" + formatearVisitados());
		
		return;
	}

    private void pintarArista(Node hijo) {

        boolean encontroCamino = false;
        for (int i = 0 ; i < visited.size(); i++) {
            Node node = visited.get(i);

            for (Connection connection : node.getConnections()) {
                if (connection.getOtherNode().equals(hijo) && !encontroCamino) {
                    connection.select();
                    encontroCamino = true;
                }
            }
        }
    }

    public void setInitialNode(int selectedNode) {
		initialNode = selectedNode; 
	}
	
    public String getAuxText(){
    	if(auxText == null || auxText.isEmpty())
    		return "";
    	
    	return auxText.get(position);
    }
	
	@Override
	public int getHighlightedWordNumber() {
		return -1;
	}

	public boolean wasDirected() {
		return directed;
	}

	public String getStartingGraphPath() {
		if(graphPaths.isEmpty())
			return "";
		return graphPaths.get(0);
	}
	
	private String formatearVisitados(){
		String visitedList = "\n ";
		
		for(Node node:visited){
			String tag = node.getTag();
			if (tag == null) { tag = Constants.sinTag;}
			visitedList += tag + " ";
		}
		
		return visitedList;
	}
	
	//para ver si es aciclico
	public boolean esAciclico(Graph g){
		
		boolean encontrado = false;
						
		for(Node start : g.getNodes()){
								
			encontrado = findCyclesStartingWith(start,start,g);
			if (encontrado)
				break;
		}
			
		if (encontrado)
			 //se encontro un ciclo -> no es aciclico
			return false;
		else
			return true;
	}
	
	private boolean findCyclesStartingWith(Node start,Node act,Graph g){
		
		if(!act.isSelected()){
			act.mark();
		}
		
		for(Connection connection : act.getConnections()){
			Node otherNode = connection.getOtherNode();
			
			boolean areEqual = otherNode.equals(start);

			if(areEqual){
				return true;				
			}

			boolean unused = !otherNode.isMarked() && !otherNode.isSelected();
			if(unused){
				if(findCyclesStartingWith(start,otherNode,g)){
					return true;							
				}
			}
		}
		return false;
	}
    
	//no se usan
	public void save(String path){
	}

	public void load(String path){
	}
}
